Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.133.131.168] |
|
Сообщ.
#1
,
|
|
|
Есть следующая задача (я не знаю, как называется тип этих задач). Имеется n наборов чисел, необходимо перераспределить числа в этих наборах так, чтобы сумма чисел в каждом наборе была равна или примерна равна.
Пример. Есть три набора: 3, 5, 1; 10, 1, 4; 12, 3, 2, 1. Общая сумма всех чисел равна 42, соответственно в каждом наборе должно быть 42/3=14. Одно из решений следующее: из третьей в первую переносим числа 3 и 2, из второй в третью переносим число 1. Получаем 3, 5, 1, 3, 2 10, 4 12, 1, 1 Насколько понимаю, эта задача типовая задача, но я не знаю как называется такая задача, поэтому в поиске найти ни чего не смог. Подскажите возможные алгоритмы решения данной задачи. |
Сообщ.
#2
,
|
|
|
Замешай все числа в кучу, после чего решай стандартную задачу распределения грузов по вагонам (ну или задача о ранце).
|
Сообщ.
#3
,
|
|
|
Спасибо.
|
Сообщ.
#4
,
|
|
|
Классические задачи этого типа имеют два параметра типа "вес" и "ценность", здесь только один....
Какие существуют алгоритмы для данной задачи? |
Сообщ.
#5
,
|
|
|
http://kladovka.net.ru/delphibase/?action=viewfunc&topic=mathalg&id=10413
|
Сообщ.
#6
,
|
|
|
Цитата Igrek @ Классические задачи этого типа имеют два параметра типа "вес" и "ценность", здесь только один.... вес = const |
Сообщ.
#7
,
|
|
|
Akina,
вот как раз этим занимаюсь раскладыванием слагаемых по кучкам, число кучек больше либо равно три, класс задачи уточняю. Но это к слову. Один рюкзак здесь не подойдёт, тут 3 рюкзака. И вообще здесь ближе не рюкзак, 3-РАЗБИЕНИЕ, NP-трудная в сильном смысле, т.е. за псевдополиномиальное время ДП её не решить. А рюкзак ДП решается куда как хорошо. Алгоритм который Mbo привёл - метод ветвей и границ, что для NP-трудной в сильном смысле естесственно. А рюкзачок - задача динамического программирования. |
Сообщ.
#8
,
|
|
|
Не могу понять, есть ли полиномиальная сводимость 3-Разбиения к данной задаче.
3-РАЗБИЕНИЕ. Условие. Заданы множество A, состоящее из 3m элементов, целое положительное число B. Элементы имеют целые положительные размеры такие, что 1. B/4 < s(a) < B/2 2. Сумма размеров всех элементов равна mB. Вопрос. Можно ли множество A разбить на m непересекающихся подмножеств так, что сумма элементов каждого i-го подмножества равна В? (и каждое подмножество содержит ровно 3 элемента). Похоже ограничения на размеры и количества даны так, чтобы исключить тривиальные случаи. Вообще, одно дело точно набирать сумму, другое дело - примерно. Примерно это как? Минимизируем среднеквадратичное отклонение по всем кучкам? Или максимальное отклонение должно быть минимально? Добавлено Igrek, это учебная задача или производственная? Для небольшой размерности она решается переборными алгоритмами, например, как предложил MBo. |
Сообщ.
#9
,
|
|
|
Swetlana, это производственная задача, область электрика. Необходим алгоритм для балансировки фаз. Есть три фазы и n автоматов, необходимо их раскидать по фазам, чтоб сила тока автоматом была более менее сбалансирована.
Важна производительность, а не оптимальность решения, достаточно решения удовлетворяющего условиям. Сейчас пробую реализовать жадный алгоритм (когда "рюкзаки" по очереди забиваем максимальными возможными элементами). Пример. 25 15 13 10 8 7 5 3 1 1 1 (уже отсортирован) ограничение будет, если округлить до минимальной погрешности <=30 Решение. Первый 25 + 3 + 1 + 1 = 30 (на каждом шаге берем максимально допустимы элемент) Второй 15 + 13 + 1 = 29 Третий 10 + 8 + 7 + 5 = 30 |
Сообщ.
#10
,
|
|
|
Алгоритм очень не оптимальный в некоторых случаях...
|
Сообщ.
#11
,
|
|
|
Цитата Igrek @ Сейчас пробую реализовать жадный алгоритм (когда "рюкзаки" по очереди забиваем максимальными возможными элементами). Попробуй наоборот, заполнять все рюкзаки одновременно, и класть наиболее тяжёлый оставшийся предмет в самый незаполненный рюкзак. |
Сообщ.
#12
,
|
|
|
Akina, попробую. По сути, так и действует человек...
|
Сообщ.
#13
,
|
|
|
Цитата Igrek @ По сути, так и действует человек... Нет, как раз чел дейтсвует так, как ты пробовал - наполняет рюкзаки по одному. |
Сообщ.
#14
,
|
|
|
Igrek, так бы сразу и сказали, что задача производственная, а вы - не студент-двоешник.
Если размерность маленькая, n<= 25, можно решить перебором, методом ветвей и границ. Для большой размерности такие задачи очень хорошо решаются локальным поиском. Я решала неоднократно. Разобранный пример с программой на паскале можно найти здесь, работы равномерно по бригадам распределяются. http://www.mesforum.ru/viewtopic.php?f=6&t=1569 |
Сообщ.
#15
,
|
|
|
Swetlana, спасибо, почитаю....
|
Сообщ.
#16
,
|
|
|
Igrek, почитайте... Вообще-то там ваша задача решена
Дипломник-заочник эту задачу делал, начал за 3 недели до защиты, ночью перед защитой презентацию доделал. Ответственности я за его программу (на си) не несу, на защите вроде работала. Открываете файл unit1.cpp, видите Цитата double P = 0.8; // процент заполненности int NNC=5; // количество контейнеров для рандома int NNT=15; // количество предметов для рандома Для вашей задачи 0,8 маловато, поставьте 0,9. Ну, и если хотите на случайных данных погонять, установите 3 контейнера (3 фазы) и своё количество автоматов (предметов). Данные, насколько мне помнится читаются из файла, в текстовом файле задаёте количество контейнеров, предметов, их размеры. Вот презентация Прикреплённый файл___________.rar (168,57 Кбайт, скачиваний: 244) |
Сообщ.
#17
,
|
|
|
Вот исполняемый файл, с его константами
Прикреплённый файлProject1.rar (432,75 Кбайт, скачиваний: 86) |
Сообщ.
#18
,
|
|
|
Вот исходники на си
Прикреплённый файлdistr.rar (255,98 Кбайт, скачиваний: 83) Добавлено Да, забыла сказать. У вас все контейнеры имеют одинаковую вместимость. а там вместимость каждого контейнера либо генерится сл. образом, либо задаётся. Наверно, в текстовом файле. |
Сообщ.
#19
,
|
|
|
Swetlana, большое спасибо!
|